home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr49 / 288_01.zip / FN.C < prev    next >
Text File  |  1993-04-01  |  3KB  |  85 lines
  1. /*
  2.         HEADER:         CUG000.07;
  3.         TITLE:          FarNeighbor, HighArc;
  4.         DATE:           Mar 89;
  5.         DESCRIPTION:    Farthest Neighbor Tour Building Algorithm;
  6.         VERSION:        1.0;
  7.         FILENAME:       FN.C;
  8.         SEE-ALSO:       TSP.C, NN.C, POPT.C, 2OPT.C, HYBRID.C, 3OPT.C;
  9.                         BOOLEAN.H, NODELIST.H, TSP.H,
  10.                         BLDMTX.C, PRTMTX.C, TIME.C;
  11.         AUTHORS:        Kevin E. Knauss;
  12. */
  13.  
  14. #include <boolean.h>
  15. #include <nodelist.h>
  16. #include <tsp.h>
  17.  
  18. long FarNeighbor (NumberOfVirteces, SavePath)
  19.    unsigned NumberOfVirteces;
  20.    NODE *SavePath;
  21. {
  22.    unsigned ArcCost();
  23.    long CircuitCost;
  24.    unsigned NewVirtex, ToIndex, CurrentVirtex, FromIndex;
  25.    BOOLEAN Available[MAXROWS][MAXCOLS];
  26.    NODE *Path;
  27.  
  28.    CircuitCost = 0;
  29.    for ( FromIndex = 1; FromIndex <= NumberOfVirteces; FromIndex++) {
  30.       for ( ToIndex = 1; ToIndex <= NumberOfVirteces; ToIndex++)
  31.          Available [FromIndex][ToIndex] = TRUE;
  32.       Available [FromIndex][FromIndex] = FALSE;
  33.    }
  34.    /* STEP 1: Find virtex from which cheapest arc eminates */
  35.       CurrentVirtex = 1;
  36.       NewVirtex = HighArc (CurrentVirtex, NumberOfVirteces, Available);
  37.       for ( FromIndex = 2; FromIndex <= NumberOfVirteces; FromIndex++) {
  38.          ToIndex = HighArc (FromIndex, NumberOfVirteces, Available);
  39.          if (ArcCost (FromIndex, ToIndex) <
  40.            ArcCost (CurrentVirtex, NewVirtex)) {
  41.             CurrentVirtex = FromIndex;
  42.             NewVirtex = ToIndex;
  43.          }
  44.       }
  45.    /* STEP 2: Establish current virtex as base of path */
  46.       Path = SavePath;
  47.       Path->position = CurrentVirtex;
  48.    /* STEP 7 Init */
  49.    do {
  50.       /* STEP 3: Set all paths unavailable to the current virtex */
  51.          for ( FromIndex = 1; FromIndex <= NumberOfVirteces; FromIndex++)
  52.             Available [FromIndex][CurrentVirtex] = FALSE;
  53.       /* STEP 4: Add cheapest arc from current virtex to cost of path */
  54.          CircuitCost += ArcCost (CurrentVirtex, NewVirtex);
  55.       /* STEP 5: Add new virtex to path */
  56.          Path = Path->next;
  57.          Path->position = NewVirtex;
  58.       /* STEP 6: Establish the new virtex as the current virtex */
  59.          CurrentVirtex = NewVirtex;
  60.       /* STEP 7: Find the next virtex at the opposite end of the cheapest
  61.                  arc from current virtex; if found, continue with step 3 */
  62.          NewVirtex = HighArc (CurrentVirtex, NumberOfVirteces, Available);
  63.    } while (Available [CurrentVirtex][NewVirtex]);
  64.    /* STEP 8: Find the cost of the arc between the new current virtex and
  65.               the initial virtex in the path and add to cost of path */
  66.       CircuitCost += ArcCost (CurrentVirtex, SavePath->position);
  67.       return (CircuitCost);
  68. } /* FarNeighbor */
  69.  
  70. unsigned HighArc (FromIndex, NumberOfVirteces, Available)
  71.    unsigned FromIndex, NumberOfVirteces;
  72.    BOOLEAN Available[MAXROWS][MAXCOLS];
  73. {
  74.    unsigned ArcCost();
  75.    unsigned ToIndex, NewIndex;
  76.  
  77.    for ( ToIndex = 1; ((ToIndex < NumberOfVirteces) &&
  78.       (!Available [FromIndex][ToIndex])); ToIndex++);
  79.    for ( NewIndex = ToIndex + 1; NewIndex <= NumberOfVirteces; NewIndex++)
  80.       if (Available [FromIndex][NewIndex])
  81.          if (ArcCost (FromIndex, NewIndex) > ArcCost (FromIndex, ToIndex))
  82.             ToIndex = NewIndex;
  83.    return (ToIndex);
  84. } /* HighArc */
  85.